public class LC0334 {
    /**
     * 时间复杂度O(N)，空间复杂度O(N)
     */
    public static boolean increasingTriplet(int[] nums) {
        int length = nums.length;
        boolean[] smallerIndicators = new boolean[length]; // 前面是否有数字比nums[i]小
        boolean[] largerIndicators = new boolean[length]; // 后面是否有数字比nums[i]大

        int minValue = nums[0], maxValue = nums[length - 1];
        for (int i = 1; i < length; i++) {
            if (nums[i] > minValue) smallerIndicators[i] = true;
            else if (nums[i] < minValue) minValue = nums[i];
            if (nums[length - 1 - i] < maxValue) largerIndicators[length - 1 - i] = true;
            else if (nums[length - 1 - i] > maxValue) maxValue = nums[length - 1 - i];
        }

        for (int i = 1; i < length - 1; i++) {
            if (smallerIndicators[i] && largerIndicators[i]) return true;
        }

        return false;
    }

    /**
     * 时间复杂度O(N)，空间复杂度O(1)
     * 参考官方题解，利用贪心，维护nums[i]左侧两个尽可能小的数字
     */
    public static boolean increasingTripletConstSpace(int[] nums) {
        int length = nums.length;
        int first = nums[0], second = 0x7FFFFFFF;
        for (int i = 1; i < length; i++) {
            if (nums[i] < first) first = nums[i];
            else if (nums[i] > first && nums[i] < second) second = nums[i];
            else if (nums[i] > second) return true;
        }

        return false;
    }
}
